package LK_Algorithm;

import java.util.Stack;

public class Alg_Day_7 {
    /*深度优先搜索考虑:栈和递归
    * 广度优先搜索考虑:队列*/
    /*图像渲染*/
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        /*先定个四个方向的顺序，例如上下左右，先上后下后左最后右
        首先找到初始节点，给它染色。
        按照方向的顺序，这里是上，就先把这个点的上方点先染色。
        一直往上一直往上，直到不符合要求，便退一步，再找这个点的下方向
        */
        int currColor = image[sr][sc];
        if (currColor != color) {
            helper(image, sr, sc, color,currColor);
        }
        return image;
    }
    public void helper(int[][] image, int sr, int sc, int newColor, int oldColor) {

        if (sr < 0 || sc < 0 || sr >= image.length || sc >= image[0].length
                || image[sr][sc] != oldColor || newColor == oldColor){
            return;
        }
        image[sr][sc] = newColor;
        helper(image, sr - 1, sc, newColor, oldColor);
        helper(image, sr + 1, sc, newColor, oldColor);
        helper(image, sr, sc - 1, newColor, oldColor);
        helper(image, sr, sc + 1, newColor, oldColor);

    }
    /*岛屿的最大面积*/

    public int maxAreaOfIsland(int[][] grid) {
            int res = 0;
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[i].length; j++) {
                    if (grid[i][j] == 1) {
                        res = Math.max(res, dfs(i, j, grid));
                    }
                }
            }
            return res;
        }
        // 每次调用的时候默认num为1，进入后判断如果不是岛屿，则直接返回0，就可以避免预防错误的情况。
        // 每次找到岛屿，则直接把找到的岛屿改成0，这是传说中的沉岛思想，就是遇到岛屿就把他和周围的全部沉默。
        // ps：如果能用沉岛思想，那么自然可以用朋友圈思想。有兴趣的朋友可以去尝试。
    private int dfs(int i, int j, int[][] grid) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[i].length || grid[i][j] == 0) {
            return 0;
        }
        grid[i][j] = 0;
        int num = 1;
        num += dfs(i + 1, j, grid);
        num += dfs(i - 1, j, grid);
        num += dfs(i, j + 1, grid);
        num += dfs(i, j - 1, grid);
        return num;

    }





}
